package gold.gold05;

/**
 * 虽然说是众数, 但是是占超过一半的数, 并不是严格的众数。
 * 可以有: 使用map存储次数O(n)但是空间也O(n);
 *          先排序然后返回中间的数即为主要元素O(nlogn)
 *          摩尔排序法, 这个好诶。
 */
public class S1710主要元素 {
    /**
     * 100, 就摩尔投票法。
     */
    public int majorityElement(int[] nums) {
        if(nums.length == 0) return -1;
        int cur = 0;
        int count = 0;
        for(int num : nums){
            if(count == 0){
                cur = num;
            }
            if(num == cur){
                count ++;
            }else{
                count --;
            }
        }
        count = 0;
        for(int num: nums){
            if(num == cur) count++;
        }
        return count > nums.length/2? cur: -1;
    }
}
